LeetCode 21、合并两个有序链表

一、题目描述

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

二、题目解析

无

三、参考代码

1、Java 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // 一开始设置一个虚拟节点，它的值为 -1，它的值可以设置为任何的数，因为我们根本不需要使用它的值
        ListNode dummy = new ListNode(-1);

        // 设置一个指针，指向虚拟节点
        ListNode pre = dummy;

        // 通过一个循环，不断的比较 l1 和 l2 中当前节点值的大小，直到 l1 或者 l2 遍历完毕为止
        while (l1 != null && l2 != null) {
            // 如果 l1 当前节点的值小于等于了 l2 当前节点的值
            if (l1.val <= l2.val) {
                // 让 pre 指向节点的 next 指针指向这个更小值的节点
                // 即指向 l1
                pre.next = l1;
                // 让 l1 向后移动
                l1 = l1.next;
            }else {
                // 让 pre 指向节点的 next 指针指向这个更小值的节点
                // 即指向 l2
                pre.next =l2;
                // 让 l2 向后移动
                l2 = l2.next;
            }
            // 让 pre 向后移动
            pre = pre.next;
        }

        // 跳出循环后，l1 或者 l2 中可能有剩余的节点没有被观察过
        // 直接把剩下的节点加入到 pre 的 next 指针位置
        
        // 如果 l1 中还有节点
        if (l1 != null) {
            // 把 l1 中剩下的节点全部加入到 pre 的 next 指针位置
            pre.next = l1;
        }

        // 如果 l2 中还有节点
        if (l2 != null) {
            // 把 l2 中剩下的节点全部加入到 pre 的 next 指针位置
            pre.next = l2;
        }

        // 最后返回虚拟节点的 next 指针
        return dummy.next;
    }
}

**2、**C++ 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        // 一开始设置一个虚拟节点，它的值为 -1，它的值可以设置为任何的数，因为我们根本不需要使用它的值
        ListNode *dummy = new ListNode(-1);

        // 设置一个指针，指向虚拟节点
        ListNode *pre = dummy;

        // 通过一个循环，不断的比较 l1 和 l2 中当前节点值的大小，直到 l1 或者 l2 遍历完毕为止
        while (l1 != NULL && l2 != NULL) {
            // 如果 l1 当前节点的值小于等于了 l2 当前节点的值
            if (l1->val <= l2->val) {
                // 让 pre 指向节点的 next 指针指向这个更小值的节点
                // 即指向 l1
                pre->next = l1;
                // 让 l1 向后移动
                l1 = l1->next;
            }else {
                // 让 pre 指向节点的 next 指针指向这个更小值的节点
                // 即指向 l2
                pre->next =l2;
                // 让 l2 向后移动
                l2 = l2->next;
            }
            // 让 pre 向后移动
            pre = pre->next;
        }

        // 跳出循环后，l1 或者 l2 中可能有剩余的节点没有被观察过
        // 直接把剩下的节点加入到 pre 的 next 指针位置
        
        // 如果 l1 中还有节点
        if (l1 != NULL) {
            // 把 l1 中剩下的节点全部加入到 pre 的 next 指针位置
            pre->next = l1;
        }

        // 如果 l2 中还有节点
        if (l2 != NULL) {
            // 把 l2 中剩下的节点全部加入到 pre 的 next 指针位置
            pre->next = l2;
        }

        // 最后返回虚拟节点的 next 指针
        return dummy->next;
    }
};

3、Python 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:

        # 一开始设置一个虚拟节点，它的值为 -1，它的值可以设置为任何的数，因为我们根本不需要使用它的值
        dummy = ListNode(-1)

        # 设置一个指针，指向虚拟节点
        pre = dummy

        # 通过一个循环，不断的比较 l1 和 l2 中当前节点值的大小，直到 l1 或者 l2 遍历完毕为止
        while l1 and l2:
            # 如果 l1 当前节点的值小于等于了 l2 当前节点的值
            if l1.val <= l2.val :
                # 让 pre 指向节点的 next 指针指向这个更小值的节点
                # 即指向 l1
                pre.next = l1
                # 让 l1 向后移动
                l1 = l1.next
            else:
                # 让 pre 指向节点的 next 指针指向这个更小值的节点
                # 即指向 l2
                pre.next =l2
                # 让 l2 向后移动
                l2 = l2.next
            
            # 让 pre 向后移动
            pre = pre.next
        

        # 跳出循环后，l1 或者 l2 中可能有剩余的节点没有被观察过
        # 直接把剩下的节点加入到 pre 的 next 指针位置
        
        # 如果 l1 中还有节点
        if l1 != None :
            # 把 l1 中剩下的节点全部加入到 pre 的 next 指针位置
            pre.next = l1
        

        # 如果 l2 中还有节点
        if l2 != None :
            # 把 l2 中剩下的节点全部加入到 pre 的 next 指针位置
            pre.next = l2;
        

        # 最后返回虚拟节点的 next 指针
        return dummy.next

四、复杂度分析

时间复杂度：O(n + m)，其中 n 和 m 分别为两个链表的长度。因为每次循环迭代中，l1 和 l2 只有一个元素会被放进合并链表中， 因此 while 循环的次数不会超过两个链表的长度之和。所有其他操作的时间复杂度都是常数级别的，因此总的时间复杂度为 O(n+m)。

空间复杂度：O(1)O(1)。只需要常数的空间存放若干变量。